package com.liunian.algorithmstudy.str;

public class Manacher {

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        char[] newChars = preprocess(chars);
        int n = newChars.length;
        int[] results = new int[n];
        int center = 0;
        int right = 0;
        for (int i = 1; i < n - 1; i++) {
            // i - center = center - i_mirror  求镜像位置索引
            int i_mirror = 2 * center - i;
            // i在right(即以center为中心，right - center 为半径)的范围内时，results[i]取i-right和results[i_mirror]最小值
            // 因为如果不取最小值，i加上半径可能会超过right
            if (i < right) {
                results[i] = Math.min(i - right, results[i_mirror]);
            }
            // 算完半径里面的，可以往right外面扩展
            while (newChars[i + 1 + results[i]] == newChars[i - 1 - results[i]]) {
                results[i]++;
            }
            // 当当前位置i加上其回文半径超过right，更新center和right
            if (results[i] + i > right) {
                center = i;
                right = i + results[i];
            }
        }
        int maxLen = 0;
        int index = 0;
        for (int i = 1; i < n - 1; i++) {
            if (results[i] > maxLen) {
                maxLen = results[i];
                index = i;
            }
        }
        int left = (index - maxLen) / 2;
        return new String(chars, left, maxLen);
    }

    private char[] preprocess(char[] chars) {
        char[] newChars = new char[2 * chars.length + 3];
        newChars[0] = '^';
        newChars[newChars.length - 1] = '$';
        newChars[newChars.length - 2] = '#';
        for (int i = 0; i < chars.length; i++) {
            newChars[2 * i + 1] = '#';
            newChars[2 * (i + 1)] = chars[i];
        }
        return newChars;
    }

}
